
#include "Link_list.h"


// 单链表的创建
Link_list * init_link_list()
{
    // 创建空间
    Link_list * L = (Link_list *)malloc(sizeof(Link_list));
    if (NULL == L)
    {
        printf("空间创建失败\n");
        return NULL;
    }
    // 初始化
    L->len = 0;
    L->next = NULL;

    // 返回创建完成的指针 动态内存空间
    return L;
    
}


// 单链表的插入
void insert_node(Link_list* list, Elenemt_data data, int index)
{
    // 安全判断
    if (NULL == list)
    {
        printf("空间不存在 无法插入\n");
        return ;
    }
    if ( index < list->len )
    {
        printf("空间不存在 无法插入\n");
        return ;
    }
    // 创建新结点
    Node * node_new = (Node *)malloc(sizeof(Node));
    node_new->data = data;
    // 头插
    if (index == 0 || list->next == NULL)
    {
        // 新结点的next 指向 头结点的 next
        node_new->next = list->next;
        // 头结点的next 指向 新结点 的地址
        list->next = node_new;
        // 迭代
        list->len++;
        return ;
    }
    // 任意位置插入
    Node * node_ptr = list->next;
    // 往后遍历
    for (size_t i = 0; i < index - 1; i++)
    {
        // 往后遍历
        node_ptr = node_ptr->next;
    }

    if (NULL == node_ptr)
    {
        printf("访问越界了\n");
        return ;
    }
    // 新结点的next 指向 遍历结点的 next
    node_new->next = node_ptr->next;
    // 遍历结点的next 指向 新结点 的地址
    node_ptr->next = node_new;

    list->len++;
    return ;
}

// 单链表的删除
Elenemt_data delete_node(Link_list* list, int index)
{
    // 创建数据
    Elenemt_data data;
    memset( &data , 0 , sizeof(data) );
    // 安全判断
    if (NULL == list)
    {
        printf("空间不存在 无法插入\n");
        return data;
    }
    if (NULL == list->next)
    {
        printf("表内无数据\n");
        return data;
    }
    if ( index < 0 || index > list->len)
    {
        printf("删除参数不对\n");
        return data;
    }
    // 头删
    Node * node_new_p = list->next;
    Node * node_new_q = node_new_p->next;
        // 在头删的时候传递的数据是 第一个结点的，所以直接赋值
    
    if (index == 0)
    {
        // 将头结点 的 next 指向第一个结点的next
        list->next = node_new_p->next;
        // 读取数据
        data = node_new_p->data;
        // 释放空间
        free(node_new_p);
        // 迭代
        list->len--;
        // 返回数据
        return data;
    }

// 中间删除
        //开始循环遍历找到  要删除结点的前一个结点
    for (int i = 0; i < index - 1; i++)
    {
        // 往后遍历
        node_new_p = node_new_p->next;
    }

    // 安全检查
    if (NULL == node_new_p || NULL == node_new_p->next)
    {
        printf("要删除的位置是空的\n");
        return data;   //注意此时的data是没有数据的
    }
    /* p 为要删除结点的前一个结点*/
    /* q 为要删除的结点*/
    // 让 q 指向要删除的结点 也就是p 的 next
    node_new_q = node_new_p->next;
    // p的 next 指向 要删除结点的next
    node_new_p->next = node_new_q->next;
    // 读取数据
    data = node_new_q->data;
    // 释放空间
    free(node_new_q);
    // 迭代
    list->len--;
    // 返回数据
    return data;
}


// 单链表的遍历
void print_link_list(Link_list* list)
{
    if (NULL == list)
    {
        printf("空间不存在 无法遍历\n");
        return ;
    }

    Node * ptr = list->next;

    for (int i = 0; ptr != NULL ; i++)
    {
        printf("姓名 %s\t性别 %s\t年龄 %d\t学号 %d\t成绩 %d\n" , 
        ptr->data.name , 
        ptr->data.sex , 
        ptr->data.age , 
        ptr->data.id ,
        ptr->data.sco);

        ptr = ptr->next;

    }
}
// 单链表的合并
/*
合表的三种形式
1、在list1 的后面 进行插入 释放list2
2、在list1 的后面 进行插入
3、创建一个新的链表 进行合表
*/

Link_list* merge_link_lists(Link_list* list1, Link_list* list2)
{
    // 安全判断
    if (NULL == list1 || NULL == list2)
    {
        printf("空间不存在 无法插入\n");
        return NULL;
    }

    // 创建新的头结点
    Link_list * list3 = init_link_list();

    // 开始插入数据  先插入 list 1 的数据
    Node * node_new = list1->next;
    int i = 0;
    for ( i = 0; node_new != NULL; i++ )
    {
        // 插入数据
        insert_node(list3 , node_new->data , i);
        // 遍历结点
        node_new = node_new->next;
    }

    // 遍历插入第二个表
    node_new = list2->next;
    for (int j = i; node_new != NULL; j++)
    {
        // 插入数据
        insert_node(list3 , node_new->data , j);
        // 遍历结点
        node_new = node_new->next;
    }
    
    // 返回新结点
    return list3;
}


// 单链表的判空
/*
    返回 true	1   代表非空
    返回 false	0   代表空
*/
bool IsEmpty_Sql_List(Link_list* list)
{
    if (NULL == list->next)
    {
        return false;
    }
    return true;
}

// 单链表的查找
Node* find_node_id(Link_list* list, int id)
{
    if (NULL == list)
    {
        printf("空间不存在 无法查找\n");
        return NULL;
    }
    if (0 == list->len)
    {
        printf("空间内无数据 无法查找\n");
        return NULL;
    }

    printf("请输入你需要查找的ID:");
    scanf("%d" , &id);

    Node * new_ptr = list->next;
    
    // 遍历查找
    for ( new_ptr = list->next; new_ptr != NULL ; new_ptr = new_ptr->next )
    {
        if (id == new_ptr->data.id)
        {
            printf("找到了 : 姓名 %s\t性别 %s\t年龄 %d\t学号 %d\t成绩 %d\n" , 
            new_ptr->data.name , 
            new_ptr->data.sex , 
            new_ptr->data.age , 
            new_ptr->data.id ,
            new_ptr->data.sco);
            return new_ptr;
        }
    }
    
    printf("查无此id\n");
    return NULL;
}

Node* find_node_name(Link_list* list)
{
    if (NULL == list)
    {
        printf("空间不存在 无法查找\n");
        return NULL;
    }
    if (0 == list->len)
    {
        printf("空间内无数据 无法查找\n");
        return NULL;
    }
    char name[128];
    printf("请输入你需要查找的名字:");
    scanf("%s" , name);

    Node * new_ptr = list->next;
    
    // 遍历查找
    for ( new_ptr = list->next; new_ptr != NULL ; new_ptr = new_ptr->next )
    {
        if (!strcmp(new_ptr->data.name , name))
        {
            printf("找到了 : 姓名 %s\t性别 %s\t年龄 %d\t学号 %d\t成绩 %d\n" , 
            new_ptr->data.name , 
            new_ptr->data.sex , 
            new_ptr->data.age , 
            new_ptr->data.id ,
            new_ptr->data.sco);
            return new_ptr;
        }
    }
    
    printf("查无此人\n");
    return NULL;
}

// 单链表的清空
void clear_link_list(Link_list* list)
{
    if (NULL == list)
    {
        printf("空间不存在 无法释放\n");
        return ;
    }
    // 遍历链表并释放结点 
    Node * ptr = list->next;
    Node * free_ptr = list->next;
    for (int i = 0; ptr != NULL ; i++)
    {   
        ptr = ptr->next;
        free(free_ptr);
        free_ptr = ptr;
    }
    list->next = NULL;
    list->len = 0;
}


// 单链表的销毁
void free_link_list(Link_list ** list)
{
    if (NULL == (*list))
    {
        printf("空间不存在 无法释放\n");
        return ;
    }
    // 遍历链表并释放结点 
    Node * ptr = (*list)->next;
    Node * free_ptr = (*list)->next;
    for (int i = 0; ptr != NULL ; i++)
    {   
        ptr = ptr->next;
        free(free_ptr);
        free_ptr = ptr;
    }

    // 释放头结点
    free(*list);
    *list = NULL;
}


